빗질 정렬

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
- 2.1. 의사 코드
- 2.2. 구현 예시
3. 개선된 알고리즘
4. 동작 예시
5. 다른 정렬 알고리즘과의 비교
참조

1. 개요

빗질 정렬은 버블 정렬의 개선된 정렬 알고리즘으로, 목록 내 멀리 떨어진 원소들을 비교하고 교환하여 정렬 속도를 향상시킨다. 빗질 정렬은 초기 간격을 목록 크기를 특정 축소 인자(일반적으로 1.3)로 나눈 값으로 설정하고, 이 간격을 점차 줄여가며 정렬을 수행한다. 간격이 1이 되면 버블 정렬과 동일하게 동작한다. 빗질 정렬은 셸 정렬과 유사하게 감소하는 간격으로 반복적인 정렬 패스를 수행하지만, 각 패스에서 배열을 완전히 정렬하지 않는다는 차이가 있다.

더 읽어볼만한 페이지

비교 정렬 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
비교 정렬 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.
정렬 알고리즘 - 합병 정렬
합병 정렬은 분할 정복 알고리즘을 사용하여 리스트를 재귀적으로 분할하고 정렬된 부분 리스트를 병합하는 비교 기반 정렬 알고리즘으로, O(n log n)의 시간 복잡도를 가지며 안정 정렬에 속하고 연결 리스트 정렬 및 외부 정렬에 유용하다.
정렬 알고리즘 - 퀵 정렬
퀵 정렬은 토니 호어가 개발한 분할 정복 방식의 효율적인 정렬 알고리즘으로, 피벗을 기준으로 리스트를 분할하여 정렬하는 과정을 재귀적으로 반복하며 다양한 최적화 기법과 변형이 존재한다.

빗질 정렬
개요
종류	정렬 알고리즘
자료 구조	배열
시간 복잡도	O(n^2)
평균 시간 복잡도	Ω(n^2/2^p), 여기서 p는 증가 수
최선 시간 복잡도	Θ(n log n)
공간 복잡도	O(1)

2. 알고리즘

빗질 정렬은 거품 정렬의 성능을 저하시키는 주요 원인인 리스트 끝부분의 작은 값, 이른바 "거북이"(거북이)^[5]를 효과적으로 제거하기 위해 고안된 알고리즘이다. 반면, 리스트 앞부분의 큰 값인 "토끼"(토끼)는 거품 정렬에서 큰 문제가 되지 않는다.

거품 정렬은 항상 인접한 두 원소, 즉 간격(gap)이 1인 원소들만 비교하고 교환한다.^[5] 빗질 정렬의 핵심 아이디어는 이 간격을 1보다 훨씬 크게 설정하여 멀리 떨어진 원소들을 비교하고 교환하는 것이다. 초기 간격은 리스트의 길이 ''n''을 축소 인자(shrink factor) ''k'' (일반적으로 1.3 사용)로 나눈 값으로 설정한다.

이 간격만큼 떨어진 원소들을 비교하고 필요시 교환하는 과정을 리스트 전체에 대해 한 번 수행한다 (이를 "빗질"한다고 표현할 수 있다). 이후, 간격을 다시 축소 인자 ''k''로 나누고, 새로운 간격으로 동일한 비교/교환 과정을 반복한다. 간격은 `n/k`, `n/k²`, `n/k³` 등과 같이 점차 줄어들어 최종적으로 1이 된다.

간격이 1이 되면, 빗질 정렬은 사실상 거품 정렬과 동일하게 동작한다. 하지만 이 단계에서는 이미 대부분의 "거북이"들이 제 위치에 가깝게 이동했기 때문에, 마지막 정렬 단계가 훨씬 효율적으로 수행된다.

축소 인자 ''k''의 값은 빗질 정렬의 효율성에 큰 영향을 미친다. 초기 제안은 4/3 (약 1.333)이었으나, 실험적 테스트를 통해 약 1.3이 이상적인 값으로 널리 사용된다. 축소 인자가 너무 작으면 불필요한 비교가 많아져 속도가 느려지고, 너무 크면 "거북이"를 효과적으로 처리하지 못해 간격이 1인 상태에서의 패스가 많아질 수 있다.

간격을 점차 줄여가며 정렬하는 방식은 셸 정렬과 유사하다. 하지만 중요한 차이점은, 셸 정렬은 각 간격 단계에서 배열이 해당 간격에 대해 완전히 정렬되도록 여러 번 패스를 수행하는 반면, 빗질 정렬은 각 간격마다 단 한 번의 패스만 수행한다는 점이다. 이 때문에 빗질 정렬은 요소를 완전히 정렬하지 않고 다음 간격으로 넘어간다. 이러한 차이로 인해 셸 정렬의 간격 시퀀스는 약 2.25 정도의 더 큰 최적 축소 인자를 가지는 경향이 있다.

추가적인 성능 개선 기법으로 "11의 규칙"이 제안되기도 했다. 이는 계산된 간격 크기가 9 또는 10일 경우, 이를 강제로 11로 설정하는 규칙이다. 이렇게 하면 특정 상황에서 "거북이"를 더 효과적으로 제거하여 최종 단계의 효율을 높일 수 있다.

알고리즘의 기본 단계는 다음과 같다:

# 초기 간격 `h`는 리스트 크기 `n`을 축소 인자(1.3)로 나눈 값의 정수 부분으로 설정한다.

# 간격 `h`를 축소 인자(1.3)로 계속 나누면서 1이 될 때까지 다음 과정을 반복한다 (필요시 "11의 규칙" 적용).

# 각 간격 `h`에 대해 리스트 전체를 한 번 순회하며 `i`번째 원소와 `i+h`번째 원소를 비교하고, 순서가 맞지 않으면 교환한다.

# 간격 `h`가 1이 된 후에는, 교환이 더 이상 발생하지 않을 때까지 간격 1로 리스트를 계속 순회하며 비교/교환한다.

2. 1. 의사 코드

function 빗질_정렬(array 입력) is 간격 := 입력.크기 // 간격 크기 초기화

축소 := 1.3 // 간격 축소 비율 설정 (일반적으로 1.3 사용)

정렬_완료 := false

loop while 정렬_완료 = false

// 다음 단계의 간격 계산

간격 := floor(간격 / 축소) // 간격을 축소 비율로 나눈 후 버림

if 간격 ≤ 1 then 간격 := 1

정렬_완료 := true // 간격이 1이고, 아래 반복문에서 교환이 없으면 정렬된 것으로 간주

else if 간격 = 9 or 간격 = 10 then 간격 := 11 // "11의 규칙": 간격이 9 또는 10이 되면 11로 설정하여 효율을 높임

end if // 현재 간격으로 리스트 전체를 확인하며 요소 교환 ("빗질")

i := 0

loop while i + 간격 < 입력.크기 // 리스트 끝까지 확인 (유사한 방식은 셸 정렬 참조)

if 입력[i] > 입력[i+간격] then // 현재 요소가 간격만큼 떨어진 요소보다 크면

스왑(입력[i], 입력[i+간격]) // 두 요소의 위치를 교환

정렬_완료 := false // 요소 교환이 발생했으므로, 다음 단계에서 다시 정렬 여부 확인 필요

end if i := i + 1

end loop end loopend function

2. 2. 구현 예시

wikitext

2. 2. 1. 파이썬

python

import math

def comb_sort(arr):

gap = len(arr)

shrink = 1.3

sorted = False

while not sorted:

gap = math.floor(gap / shrink)

if gap > 1:

sorted = False

else:

gap = 1

sorted = True

i = 0

while i + gap < len(arr):

if arr[i] > arr[i+gap]:

arr[i], arr[i+gap] = arr[i+gap], arr[i]

sorted = False

i = i + 1

return arr

2. 2. 2. Java

wikitext

public static void combSort(int[] data) {

int h = data.length * 10 / 13;

while (true) {

int swaps = 0;

for (int i = 0; i + h < data.length; ++i) {

if (data[i] > data[i + h]) {

swap(data, i, i + h);

++swaps;

}

}

if (h == 1) {

if (swaps == 0) {

break;

}

} else {

h = h * 10 / 13;

}

}

}

private static void swap(int[] a, int i, int j) {

int t = a[i];

a[i] = a[j];

a[j] = t;

}

2. 2. 3. C

wikitext

void comb_sort(int* array, int size) {

int h = size;

bool is_swapped = false;

while (h > 1 || is_swapped) {

if (h > 1) {

h = (h * 10) / 13;

}

is_swapped = false;

for (int i = 0; i < size - h; ++i) {

if (array[i] > array[i + h]) {

// swap

int temp = array[i];

array[i] = array[i + h];

array[i + h] = temp;

is_swapped = true;

}

}

}

}

3. 개선된 알고리즘

빗질 정렬의 성능을 더욱 개선하기 위해 레이시(Lacey)와 박스(Box)는 "11의 규칙"이라는 방법을 제안했다. 이 규칙은 정렬 과정에서 간격(gap) 크기를 계산할 때, 그 값이 9 또는 10이 되면 강제로 11로 설정하는 방식이다. 예를 들어, 이전 간격이 12나 13 정도였을 때 일반적인 축소 인자(약 1.3)로 나누면 간격이 9.x 또는 10.x가 될 수 있는데, 이때 간격을 11로 조정하는 것이다. 이렇게 하면 정렬 후반부까지 남아있는 작은 값, 소위 '거북이'들을 더 효과적으로 제거하여 정렬 속도를 높일 수 있다.

간격(h)이 9나 10이 되었을 때 이를 11로 처리하여 속도를 개선한 이 알고리즘을 Comb sort 11이라고 부른다. 간격이 9부터 시작하여 9 → 6 → 4 … 순서로 줄어들거나 10부터 시작하여 10 → 7 → 5 … 순서로 줄어드는 것보다, 11부터 시작하여 11 → 8 → 6 … 순서로 줄어드는 것이 요소들을 더 효율적으로 이동시켜 정렬 성능을 높이는 것으로 알려져 있다.

4. 동작 예시

다음은 숫자 배열 ''8 4 3 7 6 5 2 1''을 오름차순으로 정렬하는 예시이다.

배열의 크기 n=8이므로, 초기 간격(gap) h는 ''8 ÷ 1.3 ≒ 6''부터 시작한다.

'''h = 6'''

#: 비교: ('''8''', '''2'''), ('''4''', '''1''')

#: '''''8''' 4 3 7 6 5 '''2''' 1'' → 8과 2를 교환 → ''2 4 3 7 6 5 8 1''

#: ''2 '''4''' 3 7 6 5 8 '''1''' '' → 4와 1을 교환 → ''2 1 3 7 6 5 8 4''

#: 결과: ''2 1 3 7 6 5 8 4'' (교환 2회)

'''h = 4''' (''6 ÷ 1.3 ≒ 4'')

#: 비교: (2, 6), (1, 5), (3, 8), ('''7''', '''4''')

#: ''2 1 3 '''7''' 6 5 8 '''4''' '' → 7과 4를 교환 → ''2 1 3 4 6 5 8 7''

#: 결과: ''2 1 3 4 6 5 8 7'' (교환 1회)

'''h = 3''' (''4 ÷ 1.3 ≒ 3'')

#: 비교 결과 교환 없음.

#: 결과: ''2 1 3 4 6 5 8 7''

'''h = 2''' (''3 ÷ 1.3 ≒ 2'')

#: 비교 결과 교환 없음.

#: 결과: ''2 1 3 4 6 5 8 7''

'''h = 1''' (''2 ÷ 1.3 ≒ 1'')

#: 간격이 1이 되면 버블 정렬과 유사하게 인접한 원소를 비교하고 교환한다.

#: 비교: ('''2''', '''1'''), ('''6''', '''5'''), ('''8''', '''7''')

#: '''''2''' '''1''' 3 4 6 5 8 7'' → 2와 1을 교환 → ''1 2 3 4 6 5 8 7''

#: ''1 2 3 4 '''6''' '''5''' 8 7'' → 6과 5를 교환 → ''1 2 3 4 5 6 8 7''

#: ''1 2 3 4 5 6 '''8''' '''7''' '' → 8과 7을 교환 → ''1 2 3 4 5 6 7 8''

#: 결과: ''1 2 3 4 5 6 7 8'' (교환 3회)

이 예시에서는 총 6번의 교환으로 정렬이 완료되었다.

5. 다른 정렬 알고리즘과의 비교

빗질 정렬은 버블 정렬의 비효율성을 개선하기 위해 제안된 정렬 알고리즘이다. 버블 정렬의 주요 문제점은 리스트 끝부분에 위치한 작은 값들, 이른바 '거북이'를 제자리로 옮기는 데 시간이 매우 오래 걸린다는 점이다. 반면 리스트 앞부분의 큰 값인 '토끼'는 비교적 빠르게 제자리로 이동하므로 큰 문제가 되지 않는다.

버블 정렬은 항상 서로 인접한 두 요소, 즉 간격(gap)이 1인 요소들만 비교하고 교환한다.^[5] 빗질 정렬의 핵심 아이디어는 이 간격을 1보다 훨씬 크게 설정할 수 있다는 것이다. 처음에는 리스트의 전체 길이 ''n''에 가까운 큰 간격으로 시작하여, 정렬 과정을 반복하면서 간격을 점차 줄여나간다. 간격은 '축소 인자(shrink factor)' ''k''(일반적으로 1.3 사용)를 사용하여 줄어든다. 즉, 각 단계마다 이전 간격을 ''k''로 나눈 값을 새로운 간격으로 사용하며, 이 과정을 간격이 1이 될 때까지 반복한다.

간격이 1이 되면 빗질 정렬은 버블 정렬과 동일하게 동작한다. 하지만 이때는 이미 대부분의 '거북이'들이 제자리 근처로 옮겨진 상태이므로, 마지막 단계의 버블 정렬 과정은 비교적 효율적으로 수행될 수 있다. 축소 인자 ''k''의 값은 알고리즘의 성능에 중요한 영향을 미치는데, 실험적으로 1.3 정도가 적절한 것으로 알려져 있다. ''k'' 값이 너무 작으면 불필요한 비교가 많아지고, 너무 크면 '거북이'를 효과적으로 처리하지 못할 수 있다.

간격을 점차 줄여가며 정렬한다는 점에서 빗질 정렬은 셸 정렬과 유사점을 가진다. 하지만 중요한 차이점은, 셸 정렬은 특정 간격에 대해 부분 리스트들이 완전히 정렬될 때까지 반복 작업을 수행한 후 다음 간격으로 넘어가는 반면, 빗질 정렬은 각 간격 단계에서 전체 리스트에 대해 한 번의 패스만 수행하고 바로 다음 간격으로 넘어간다는 점이다. 즉, 빗질 정렬의 각 패스는 리스트를 완전히 정렬하지 않는다. 이러한 차이로 인해 셸 정렬의 최적 간격 감소율(축소 인자에 해당)은 빗질 정렬보다 더 큰 값(약 2.25)을 가진다.

빗질 정렬이 버블 정렬을 개선하는 방식은, 간격(gap) 개념을 도입하여 성능을 향상시킨다는 점에서 삽입 정렬을 개선하여 셸 정렬을 만든 것과 유사한 접근법으로 볼 수 있다.

참조

_[1] 논문 Analyzing variants of Shellsort 2001-09-15
_[2] 논문 An efficient variation of bubble sort 1980-08-29
_[3] 뉴스 A Fast, Easy Sort: A novel enhancement makes a bubble sort into one of the fastest sorting routines https://web.archive.[...] 1991-04
_[4] 웹사이트 diminishing increment sort https://xlinux.nist.[...] 2021-03-09
_[5] 웹사이트 comb sort https://xlinux.nist.[...] 2021-03-09
_[6] 논문 An efficient variation of bubble sort
_[7] 논문 Analyzing variants of Shellsort
_[8] 간행물 A Fast Easy Sort http://cs.clackamas.[...] Byte Magazine 1991-04
_[9] 논문 Analyzing variants of Shellsort 2001-09-15
_[10] 논문 An efficient variation of bubble sort
_[11] 간행물 A Fast Easy Sort http://cs.clackamas.[...] Byte Magazine 1991-04

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com